package com.zang.array;

/**
 * @author ZVerify
 * @since 2022/10/04 17:33
 * @see <a href="https://leetcode.cn/problems/minimum-window-substring/">...</a>
 **/
public class 最小覆盖子串 {

    // hard

    public String minWindow(String s, String t) {

        // 用于保存26个英文字母
        int[] cnt = new int[128];

        // 将t中的字母放进去
        for (char c:t.toCharArray()){
            cnt[c]++;
        }


        // 保存存在的左边界
        int form = 0;
        // 当前窗口中缺少几个字符
        int total = t.length();
        int min = Integer.MAX_VALUE;

        for (int j = 0, i = 0;j < s.length();j++){
            // 一旦发现 出现了t中存在的字母都将total--，并且将当前窗口中存缺不缺少他进行变化为0则不缺少
            if (cnt[s.charAt(j)]-- > 0){
                total--;
            }
            // 如果一个都不缺了说明已经达到要求
            while (total == 0){
                System.out.println(s.substring(form,form+j-i+1));
                if (j-i+1 < min){
                    min = j-i+1;
                    form = i;
                }
                // 如果当前位置等于0
                if (++cnt[s.charAt(i++)] > 0){
                    total++;
                }
            }
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(form,form+min);
    }
}
